#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#include <stddef.h>
using ElementType = int;
class LinkList
{
public:
    // 无参构造
    LinkList();
    // 拷贝构造
    LinkList(const LinkList &list);
    // 析构
    ~LinkList();

    // 尾插
    void InsertTail(const ElementType &element);
    // 头插
    void InsertHead(const ElementType &element);
    // 中间插
    void InsertByIndex(int index, const ElementType &element);

    // 按位置删
    void RemoveByIndex(int index);
    // 按值删
    void RemoveByElement(const ElementType &element);

    // 按位置修改
    void UpdateByIndex(int index, const ElementType &element);
    // 按值修改
    void UpdateByElement(const ElementType &oldValue, const ElementType &newValue);

    // 冒泡排序
    void BubbleSort();
    // 归并
    LinkList Merge(const LinkList &list);
    // 排序
    void Sort();

    // 链表逆序（三指针）（手撕！！！）
    void Reserve();
    // 逆序（递归）
    void Reserve2();
    // show
    void show();

private:
    // 对外展示的是链表本身，节点不对外展示
    // 节点（数据域+指针域）
    struct Node
    {
        Node(const ElementType &value):value(value), next(nullptr){} // 构造函数（构造一个全新的节点）
        ElementType value; // 数据域
        Node *next; // 指针域
    };
    void FastSort(Node *start, Node *end);
    Node *Reserve2(Node *node);
    Node *head; // 头指针
    size_t size; // 节点个数

};

#endif